package QuestionDaily;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class RangeModule {
    /**
     * Range模块是跟踪数字范围的模块。
     * 设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
     */

    /**
     * 思路是维护一个集合，存储每组边界
     * 思路清晰，实现混乱繁琐
     * 只能通过一半的测试用例
     */
  /**  List<int[]> range;
    public RangeModule() {
        range=new ArrayList<>();
    }
    public void addRange(int left, int right) {
        right--; //右边是开区间
        int l_idx = 0, r_idx = 0;
        int l_location = 0, r_location = 0; //说明该边界值所处区间的位置，1左 ，2中
        int index = 0;
        for (; index < range.size(); index++) {    //遍历所有边界。找到左边界的位置
            if (left < range.get(index)[0]) { //左值小于当前位置区间的左边界
                l_idx = index;
                l_location = 1;
                break;
            } else if (left < range.get(index)[1]) { //左值在当前区间内
                l_idx = index;
                l_location = 2;
                break;
            }
        }
        for (; index < range.size(); index++) {    //继续遍历所有边界。找到右边界的位置
            if (right < range.get(index)[0]) { //右边界小于当前位置区间的左边界
                r_idx = index;
                r_location = 1;
                break;
            } else if (right < range.get(index)[1]) { //左值在当前区间内
                r_idx = index;
                r_location = 2;
                break;
            }
        }
        if (l_location == 0) {   //等于0，说明没有可以插入的位置，直接加到尾部
            range.add(new int[]{left, right});
        } else {
            if (l_location == 2 && l_idx == r_idx && r_location == 2) //在一个区间的内部，无需操作
                return;
            //对区间放进去集合
            List<int[]> ans = new ArrayList<>();
            int i = 0, newL = 0, newR = 0;
            for (; i < l_idx; i++)
                ans.add(range.get(i));
            newL = l_location == 1 ? left : range.get(i)[0];
            if (r_location == 1) {  //如果right的位置在下一个区间的左边
                if(right+1==range.get(r_idx)[0]){ //如果right和下一个区间是连续的
                    newR=range.get(r_idx)[1];       //合并区间
                    i = r_idx+1; //下一个添加r_idx+1
                } else {
                    newR = right;
                    i = r_idx; //下一个添加r_idx
                }
            } else {
                newR = range.get(i)[1];
                i = r_idx + 1;
            }
            ans.add(new int[]{newL,newR});
            for (; i < range.size(); i++) {
                ans.add(range.get(i));
            }
            range=ans;
        }
    }

    public boolean queryRange(int left, int right) {
        right--;
        for (int i = 0; i < range.size(); i++) {    //遍历所有边界。找到左边界的位置
            if (left >= range.get(i)[0] &&left <= range.get(i)[1] ) { //左值在当前位置区间内
                if(right<=range.get(i)[1]) //右值在区间内
                    return true;
                else
                    return false;
            }
        }
        return false;
    }

    public void removeRange(int left, int right) {
        right--; //右边是开区间
        int l_idx = 0, r_idx = 0;
        int l_location = 0, r_location = 0; //说明该边界值所处区间的位置，1左 ，2中
        int index = 0;
        for (; index < range.size(); index++) {    //遍历所有边界。找到左边界的位置
            if (left < range.get(index)[0]) { //左值小于当前位置区间的左边界
                l_idx = index;
                l_location = 1;
                break;
            } else if (left <= range.get(index)[1]) { //左值在当前区间内
                l_idx = index;
                l_location = 2;
                break;
            }
        }
        for (; index < range.size(); index++) {    //继续遍历所有边界。找到右边界的位置
            if (right < range.get(index)[0]) { //右边界小于当前位置区间的左边界
                r_idx = index;
                r_location = 1;
                break;
            } else if (right <= range.get(index)[1]) { //右值在当前区间内
                r_idx = index;
                r_location = 2;
                break;
            }
        }

        if (l_location != 0) {   //不等于0，说明有可以删除的位置
            List<int[]> ans = new ArrayList<>();
            int i = 0;
            for (; i < l_idx; i++)
                ans.add(range.get(i));
            if (l_location == 1) {//left如果位于该区间的左边,只用看right的位置
                if (r_location == 1)//right也在某个区间的左边
                    i = r_idx;    //跳过 r_idx之前的区间
                else {
                    range.get(i)[0] = right;
                    ans.add(range.get(i));
                    i = r_idx + 1; //跳过包括 r_idx之前的区间
                }
            } else {//left如果位于该区间的内部
                if (r_location == 1) {//right在某个区间的左边
                    range.get(i)[1] = left-1;
                    ans.add(range.get(i));
                    i = r_idx;    //跳过 r_idx之前的区间
                } else {//right在某个区间的内部
                    if(left!=range.get(i)[0])
                        ans.add(new int[]{range.get(i)[0], left-1}); // left-1和right+1是去掉本身位置
                    if(right!=range.get(i)[1])
                        ans.add(new int[]{right+1, range.get(r_idx)[1]});
                    i = r_idx + 1; //跳过包括 r_idx之前的区间
                }
                for (; i < range.size(); i++) {
                    ans.add(range.get(i));
                }
                range = ans;
            }
        }
    }
   */


    /**
     * 维护一个线段树，其中包含所有可以覆盖的节点
     * 每个节点的值表示当前区间是否被覆盖
     */
    public RangeModule() {}

    /**
     *添加区间
     */
    public void addRange(int left, int right) {
        // 1 表示复盖；-1 表示取消覆盖
        update(root, 1, N, left, right - 1, 1);
    }

    /**
     * 删除区间
     */
    public void removeRange(int left, int right) {
        // 1 表示复盖；-1 表示取消覆盖
        update(root, 1, N, left, right - 1, -1);
    }
    /**
     *查询区间
     */
    public boolean queryRange(int left, int right) {
        return query(root, 1, N, left, right - 1);
    }

    // *************** 下面是模版 ***************
    class Node {
        Node left, right;
        boolean cover;// 表示当前区间是否被覆盖
        int add;  //懒惰标记，表示该节点所有对应的孩子节点都应该被覆盖
    }
    private int N = (int) 1e9;  //最大范围
    private Node root = new Node(); //根节点

    /**
     * 线段树的更新
     * 在区间 [start, end] 中对区间 [l, r] 的节点进行覆盖，将区间 [l, r] 的cover都设为true
     * @param val
     */
    public void update(Node node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            // 1 表示覆盖；-1 表示取消覆盖
            node.cover = val == 1;
            node.add = val;
            return ;
        }
        int mid = (start + end) >> 1;
        //把当前节点的懒惰标记下推到所有子节点
        pushDown(node);
        //递归覆盖区间的所有节点
        if (l <= mid) update(node.left, start, mid, l, r, val);
        if (r > mid) update(node.right, mid + 1, end, l, r, val);
        //向上更新懒惰标记
        pushUp(node);
    }

    /**
     *查询区间
     */
    public boolean query(Node node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node.cover;
        int mid = (start + end) >> 1;
        //把当前节点的懒惰标记下推到所有子节点
        pushDown(node);
        // 查询左右子树是否被覆盖
        boolean ans = true;
        if (l <= mid) ans =  query(node.left, start, mid, l, r);
        if (r > mid) ans = ans && query(node.right, mid + 1, end, l, r); //如果左子树未被覆盖，直接返回ans，无需查询右子树
        return ans;
    }
    private void pushUp(Node node) {
        // 向上更新，左右孩子节点都被覆盖，该节点才是被覆盖区间
        node.cover = node.left.cover && node.right.cover;
    }

    /**
     * 下推懒惰标记
     * 创建左右孩子节点
     */
    private void pushDown(Node node) {
        //如果节点不存在左右孩子节点，那么我们就创建左右孩子节点
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return ; //不需要覆盖则返回
        //完成覆盖
        node.left.cover = node.add == 1;
        node.right.cover = node.add == 1;
        // 把需要覆盖的标记下推给孩子节点
        node.left.add = node.add;
        node.right.add = node.add;
        // 取消当前节点标记
        node.add = 0;
    }

}